struct GraphEdge
{
    GraphEdge() {}
    GraphEdge(UINT v0, UINT v1, float _weight)
    {
        v[0] = v0;
        v[1] = v1;
        weight = _weight;
    }

    inline UINT GetOtherVertex(UINT v0) const
    {
        if(v[0] == v0)
        {
            return v[1];
        }
        else
        {
            return v[0];
        }
    }

    UINT v[2];
    float weight;
};

struct GraphVertex
{
    vector<UINT> edges;

    //
    // Internal values used by Dijkstra's algorithm
    //
    float dist;
    int predecessorEdgeIndex;
    bool visited;
};

class Graph
{
public:
    Graph();
    Graph(const vector<GraphEdge> &edges);
    
    void FreeMemory();

    void LoadEdges(const vector<GraphEdge> &edges);

    vector<UINT> ShortestPath(UINT startVertex, UINT endVertex);

    inline const vector<GraphEdge>& Edges()
    {
        return _edges;
    }

private:
    int _cachedVertex;

    void GenerateAdjacencyList();
    UINT HighestVertexIndex();

    vector<GraphEdge> _edges;
    vector<GraphVertex> _vertices;
};
